ASICs and FPGAs are used to implement large systems that include million of gates and megabits of embedded memory. The complexity of large systems often requires the use of EDA tools to create and optimize a design for the system onto physical target devices. Among the procedures performed by EDA tools in a computer aided design (CAD) flow are synthesis, technology mapping, clustering, placement, and routing.
In the past, physical synthesis was optionally used to perform a series of circuit transformations to optimize the design of the system. Physical synthesis would typically be performed at a single point after placement and before routing to improve the delays on connections to be routed. Estimates of interconnect delay obtained from existing placement could be used to guide physical synthesis transformations that restructure the circuit on or near a critical path. Unlike traditional synthesis, physical synthesis may take into account the technology and architecture of the target device and delays associated with signals on the target device while performing the circuit transformations to optimize the design of the system.
Hill-climbing is an optimization technique which may be used in physical synthesis. Hill-climbing attempts to maximize (or minimize) a function f(x), where x are discrete states. These states are typically represented by vertices in a graph, where edges in the graph encode nearness or similarity of a graph. Hill-climbing will follow the graph from vertex to vertex, always locally increasing (or decreasing) the value of f, until a local maximum xm is reached. Hill-climbing has proven to be highly beneficial in improving the quality of optimization results. However, when performing hill-climbing, a large amount of time may be spent performing iterations that may turn out to be useless when an old, better solution is restored.
Thus, what is needed is an efficient and effective method and apparatus for performing hill-climbing in applications such as physical synthesis.